import math
from util import *
import random
import numpy as np
class DRR:
    #没有服务删除和部署的过程，一开始就进行初始化部署，然后后续不进行改变。
    def __init__(self, cloud_system):
        self.cloud_system=cloud_system
        self.env=cloud_system.env
        self.request_to_replica_info={}
        return
    
    def init_deploy(self):
        
        if self.cloud_system.args.GSMS_init_deploy_flage:  #根据微服务call频率，按比例得到不同类型微服务数量，且在随机选择node进行部署。
            #基于类型，统计邻接矩阵
            ms_kind_list=self.cloud_system.ms_kind_list
            ms_kind_adj=np.zeros((len(ms_kind_list), len(ms_kind_list)))
            for service_name in self.cloud_system.service_to_callgraph_dict.keys():
                request_t=self.cloud_system.service_to_callgraph_dict[service_name]
                for task_t in request_t.start_task_list:
                    self.get_adj_matrix_update_ms_kind_adj(task_t, ms_kind_adj, ms_kind_list)
            #获取每个类型的微服务有多少个
            ms_call_num=ms_kind_adj.sum(axis=1)
            all_ms_num=self.cloud_system.args.bare_metal_node_num*self.cloud_system.args.ms_number_for_each_node
            ms_index_list=random.choices(population=range(len(ms_call_num)),weights=ms_call_num,k=all_ms_num-len(ms_kind_list))
            #基于类型统计的邻接矩阵，计算计划生成的微服务call 邻接矩阵
            ms_list=ms_kind_list.copy()
            for index in ms_index_list:
                ms_list.append(ms_kind_list[index])
                
            #对于未部署的微服务进行部署
            for ms_kind in ms_list:
                node_index_list=[i for i in range(self.cloud_system.args.bare_metal_node_num)]
                while True:
                    node_index=random.choice(node_index_list)
                    result, ms_id, node_id= self.cloud_system.bare_metal_node_list[node_index].deploy_ms(ms_kind, without_cold_start=True)
                    if result==False:
                        node_index_list.remove(node_index)
                        if len(node_index_list)==0:
                            a=1
                        assert len(node_index_list)>0
                        continue
                    else:
                        ms_obj=self.cloud_system.bare_metal_node_list[node_index].msid_to_msobj[ms_id]
                        
                        break
                    
        return
    
    def get_adj_matrix_update_ms_kind_adj(self,task, ms_kind_adj, ms_kind_list):
        for sub_task in task.sub_task_list:
            task_index=ms_kind_list.index(task.ms_kind)
            sub_task_index=ms_kind_list.index(sub_task.ms_kind)
            call_num=task.call_num
            ms_kind_adj[task_index][sub_task_index]+=call_num
            ms_kind_adj[sub_task_index][task_index]+=call_num
            self.get_adj_matrix_update_ms_kind_adj(sub_task, ms_kind_adj, ms_kind_list)
    
#************************************************************************************************************    
    #调度入口函数
    def do_schedule_deploy(self):
        not_scheduled_tasks=[]
        for task in self.cloud_system.pending_task_queue:
            if task.request.reject_flage==True:
                continue
            #添加对subdeadline的评估计算
            deadline=task.request.deadline
            base_request=self.cloud_system.service_to_callgraph_dict[task.request.service_name]
            self.schedule_DRR_get_subdeadline(task.request, base_request, deadline)
            #判断是否直接拒绝
            for entry_task in task.request.start_task_list:
                if entry_task.deal_time>entry_task.sub_deadline:
                    task.reject_flage=True
                    task.back()
                    continue
            
            aim_ms_list=self.schedule_DRR_get_replica(task.request, task, base_request)
            if len(aim_ms_list)==0:
                task.reject_flage=True
                task.back()
                continue
            
            result=self.schedule_DRR_select_ms(task, aim_ms_list)
            
            if result==False:
                not_scheduled_tasks.append(task)
        #清空队列
        self.cloud_system.pending_task_queue=not_scheduled_tasks
        
        return
    
    def schedule_DRR_get_subdeadline(self, request, request_base, deadline):
        if request.generate_sub_deadline_flage==True:
            return
        request.generate_sub_deadline_flage=True
        waiting_deal_task_list=[]
        dealed_task_list=[]
        ms_record_for_task={} #task_id to ms_obj
        for task in request_base.task_id_to_obj.values():
            #首先找到最低端的task
            if len(task.sub_task_list)==0:
                waiting_deal_task_list.append(task)
                
        while len(waiting_deal_task_list)>0:
            task_t=waiting_deal_task_list.pop(0) 
            if len(task_t.sub_task_list)==0 or list_is_sub_of_another_list(task_t.sub_task_list, dealed_task_list):
                ms_obj_list=self.cloud_system.get_available_ms_obj_with_ms_kind(task_t.ms_kind)
                if len(ms_obj_list)==0:
                    aim_ms_obj=None
                else:
                    #这里选择微服务主要是为了计算通信时间TT
                    aim_ms_obj=self.cloud_system.rng_general.choice(ms_obj_list)
                
                min_succ_sub_deadline=deadline
                for succ_task in task_t.sub_task_list:
                    if succ_task.task_id in ms_record_for_task.keys():
                        succ_task_ms_obj=ms_record_for_task[succ_task.task_id]
                    else:
                        succ_task_ms_obj=None
                    #原始方法是针对异构机器，找处理能力最快的机器，这里进行调整，由于本文中都是同构机器，如果有一方没有存在的微服务，则TT=0
                    TT=self.cloud_system.get_TT_time(succ_task, succ_task_ms_obj, aim_ms_obj)
                    succ_sub_deadline=succ_task.sub_deadline
                    min_succ_sub_deadline=min(min_succ_sub_deadline, succ_sub_deadline-TT-succ_task.ave_deal_time)
                task_t.sub_deadline=min_succ_sub_deadline
                dealed_task_list.append(task_t)
                ms_record_for_task[task_t.task_id]=aim_ms_obj
                if task_t.parent_task != None and task_t.parent_task not in waiting_deal_task_list:
                    waiting_deal_task_list.append(task_t.parent_task)
            else:
                waiting_deal_task_list.append(task_t) 
                
        #前面其实已经生成完subdeadline，后面需要将base的结果赋值给当前的request
        for task_obj in request.task_id_to_obj.values():
            task_obj.sub_deadline=request_base.task_id_to_obj[task_obj.task_id].sub_deadline
        
        return
    
    
    def schedule_DRR_get_replica(self, request, task_t, request_base):
        request_reliability=self.cloud_system.service_to_reliability[request_base.service_name]
        task_t.ave_deal_time=request_base.task_id_to_obj[task_t.task_id].ave_deal_time
        #由于不清楚有多少个task，因此来一个计算一个副本数量
        if request not in self.request_to_replica_info.keys():
            
            all_task_num=len(request_base.task_id_list)
            all_ready_num=0
            all_ready_reliability=1
        else:
            all_task_num=self.request_to_replica_info[request]["all_task_num"]
            all_ready_num=self.request_to_replica_info[request]["all_ready_num"]
            all_ready_reliability=self.request_to_replica_info[request]["all_ready_reliability"]
        
        #获取当前task需要的可靠性大小
        current_up_relia=math.pow(request_reliability/all_ready_reliability, 1/(all_task_num-all_ready_num))
        if current_up_relia>=1:
            return []
        #获取指定微服务故障参数
        ms_lambda=self.cloud_system.ms_kind_to_transient_lambda[task_t.ms_kind]
        #获取单个task无故障概率
        single_reliability=get_reliability_without_failure(task_t.deal_time, ms_lambda)
        #获取副本数量
        replica_num=get_aim_replica_num(current_up_relia, single_reliability)
        
        
        #获取所有正在运行的微服务列表
        ms_obj_list=self.cloud_system.get_available_ms_obj_with_ms_kind(task_t.ms_kind)
        aim_ms_obj_list=[]
        for ms_obj in ms_obj_list:
            if replica_num==0:
                break
            TT=self.cloud_system.get_TT_time(task_t, ms_obj, task_t.first_parent_ms_obj)
            if ms_obj.get_estimate_end_time()+TT+request_base.task_id_to_obj[task_t.task_id].ave_deal_time<= task_t.sub_deadline:
                aim_ms_obj_list.append(ms_obj)
                replica_num-=1
        
        all_ready_num+=1
        all_ready_reliability=all_ready_reliability*(1-math.pow(1-single_reliability, len(aim_ms_obj_list)))
        new_info={}
        new_info["all_task_num"]=all_task_num
        new_info["all_ready_num"]=all_ready_num
        new_info["all_ready_reliability"]=all_ready_reliability
        self.request_to_replica_info[request]=new_info
        return aim_ms_obj_list
            

    
    #为task选择微服务
    def schedule_DRR_select_ms(self, task, ms_obj_list):
        #获取所有正在运行的微服务列表
        for ms_obj in ms_obj_list:
            self.cloud_system.env.process(ms_obj.put_task_to_queue_event(task)) 
            task.aim_ms_obj_list.append(ms_obj)
            
            
